/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */

#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
   leaves = new BTLeafNode[20];
   leavessize = 20;
   nonleaves = new BTNonLeafNode[20];
   nonleavessize = 20;
   leavescount = 0;
   nonleavescount = 0;
   treeHeight = 0;
   pageIdcount = 1;
   rootPid = -1;
}

BTreeIndex::BTreeIndex(const string& indexname, char mode)
{
   leaves = new BTLeafNode[20];
   leavessize = 20;
   nonleaves = new BTNonLeafNode[20];
   nonleavessize = 20;
   leavescount = 0;
   nonleavescount = 0;
   treeHeight = 0;
   pageIdcount = 0;
   rootPid = -1;
   pageIdcount = 1;
   open (indexname, mode);
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
   RC   rc;
   char page[PageFile::PAGE_SIZE];

  // open the page file
   if ((rc = pf.open(indexname, mode)) < 0) return rc;

  // the file is empty, in that case return 0, otherwise, read the nodes into the array
   if(pf.endPid() == 0)
      return 0;
   else 
   {
      BTNode determine;
      pageIdcount = pf.endPid();

      determine.read(0, pf); // 0th page with the extra info
      rootPid = determine.buff[0];
      treeHeight = determine.buff[1];

      for (int i = 1; i < pf.endPid(); i++) // how do i know what to read into? leaves/nonleaves?
      {
         determine.read(i, pf);
         if(determine.buff[255] == -99)
         {
	    nonleaves[nonleavescount].read(i, pf);
            NonLeafIds[nonleavescount] = i;
            nonleavescount++;
         }
         else
         {
	    leaves[leavescount].read(i, pf);
            LeafIds[leavescount] = i;
            leavescount++;
         }
      }
   }
   return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
   index.pid = index.eid = 0;
   int page[256];
   page[0] = rootPid;
   page[1] = treeHeight;
   pf.write(0, page); // arbitrary page
   
   int x = 1;
   for(int i = 0; i < leavescount; i++) //writing the leaves
   {
     pf.write(x, leaves[i].buff);
     x++;
   }
   for(int j = 0; j < nonleavescount; j++) //writing the nonleaves
   {
     pf.write(x, nonleaves[j].buff);
     x++;
   }
   return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 // call initally with root id, root id, and height = treeheight, flag = false, insertcount = 0
 // past is used to store the past id when flag = false, and the id to insert once flag = true
 */

 // put in page id, get out the index where it is sotred

int BTreeIndex::getindex(int id, bool flag) //false is for leaves, true for nonleaves
{
   if(!flag)
      for (int i = 0; i < leavescount; i++) // number of leaves = number of id entries
         if(id == LeafIds[i])
            return i;
   else
      for (int i = 0; i < nonleavescount; i++)
         if(id == NonLeafIds[i])
            return i;
   return -1;
}

 /// ATM this code does not: resize some of the arrays if they overflow
 //PageId in is the pageid you are currently at
 //PageId past is the pageid you were just at

RC BTreeIndex::insert(int key, const RecordId& rid, PageId in, PageId past, int height, bool flag, int insertcount)
{
   index.pid = in; // page id to start at
   index.eid = 0;
   int myheight = height; // the current height
   if(nonleavescount == 0) // so far only one leaf is the whole tree
   {
      if(leaves[0].getKeyCount() < 85) // no overflow
      {
         leaves[0].insert(key, rid);
         LeafIds[0] = 1;
         pageIdcount++;

         return 0;
      }
      else // you will need to split the node
      {
         int nonleafkey = 0; // the 1st key of the new node
         leaves[0].insertAndSplit(key, rid, leaves[1], nonleafkey); // insert the new value
            // setting the leaf ids
         leaves[0].setNextNodePtr(1);

         LeafIds[1] = 2;
         leavescount++; // counts the number of leaves, which I will use as the number of nonleaves
         pageIdcount++; // 0th id set, set 1st id, set pageIdcount to the next one

            // creating the non leaf (now a root)
         if (nonleavescount == nonleavessize) // if the array is too small
         {
            delete[] nonleaves;
            nonleaves = new BTNonLeafNode[2*leavescount]; // wont ever have more non leaves than leaves
         }

         nonleaves[0].initializeRoot(0,nonleafkey, 1); // set up the nonleaf
         
         NonLeafIds[0] = 3; // put its id in the list
         rootPid = 3; // it is now the root
         nonleavescount++; // non leaves count is now 1
         treeHeight++; // treeHeight is now 1
         pageIdcount++; // pageIdcount is now 3

         return 0;
      }
   }
   else if(nonleavescount > 0 && flag == false) //there are non leaves
   {
      int nextid; // the next id to look at

      nonleaves[getindex(index.pid, true)].locateChildPtr(key, nextid); // get the child pointer
      myheight--; // you just went down a level
      if(myheight = 0) // you've reached the leaves
      {
         int leafind = getindex(nextid,false); // the leaf index of the child
         if(leaves[leafind].getKeyCount() < 85) // if it fits the leaf insert it
            leaves[leafind].insert(key, rid);
         else // if it doesnt, overflow the leaf, split
         {
            int nonleafkey = 0;
            leaves[leafind].insertAndSplit(key, rid, leaves[leafind+1], nonleafkey);
            leaves[leafind].setNextNodePtr(pageIdcount);
                /* the original leaf should already have these set
                leaves[index.pid].thispageid = pageIdcount;
                pageIdcount++;
                */

            LeafIds[leafind+1] = pageIdcount;
            pageIdcount++;
            leavescount++;

            insert(nonleafkey, rid, rootPid, index.pid, treeHeight-1, true, 1); // insert to non leaf
                // past becomes the id to insert into ie the previous id
         }
      }
      else
         insert(key, rid, nextid, index.pid, myheight-1, false, insertcount );
   }
   else if (insertcount != treeHeight &&flag == true) // insert the nonleaves
   {
      int nonleafind = getindex(index.pid, true); // the nonleafindex that you are currently at
      if(myheight == 0) //reached where you want to go, insert it
      {
         if(nonleaves[nonleafind].getKeyCount() < 127) //it fits into the
            nonleaves[nonleafind].insert(key, past);
         else // overflow the nonleaf
         {
            int midkey = 0;
            nonleaves[nonleafind].insertAndSplit(key, past, nonleaves[nonleafind+1], midkey);
                //nonleaves[nonleafind+1].thispageid = pageIdcount;
            NonLeafIds[nonleafind+1] = pageIdcount;
            pageIdcount++;
            nonleavescount++;
            insertcount++; // now youve inserted one more nonleaf
            if ((treeHeight - insertcount) != 0) // no need to make a root
               insert(midkey, rid, rootPid, index.pid, treeHeight-insertcount, true, insertcount);
            else // make a new root
            {
               nonleaves[nonleavescount].initializeRoot(NonLeafIds[nonleafind], midkey, NonLeafIds[nonleafind+1]);
	       treeHeight++;
            }
         }
      }
      else // must traverse down the tree.
      {
         int nextid;
         nonleaves[nonleafind].locateChildPtr(key, nextid);
         insert(key, rid, nextid, index.pid, myheight-1, true, insertcount);
      }

   }
   if(flag == false)
      past = index.pid;
   return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
   RC rc;
   PageId nextpage;
   if(rootPid > 0)
     nextpage = rootPid;
   else
     nextpage = 1; // the leaf page if only one leaf

   //cout << treeHeight << endl; - this doesnt appear

   for (int i = 0; i < treeHeight; i++)
      rc = nonleaves[getindex(nextpage, true)].locateChildPtr(searchKey, nextpage);
   if (rc < 0)
      return rc;
   leaves[getindex(nextpage, false)].locate(searchKey, cursor.eid);
   cursor.pid = nextpage;

   return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */

 // What does forward mean? if eid = 2 is forward eid = 3 or eid = 1
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
   if(cursor.eid == (leaves[getindex(cursor.pid, false)].buffcount) -1)
   {
      //because the buffcount is the index of the next available buffer slot
      cursor.pid = leaves[getindex(cursor.pid, false)].getNextNodePtr();
      cursor.eid = 0;
   }
   else
     cursor.eid++;

   key = leaves[getindex(cursor.pid, false)].buff[3*(cursor.eid)];
   rid.pid = leaves[getindex(cursor.pid, false)].buff[(3*(cursor.eid))+1];
   rid.sid = leaves[getindex(cursor.pid, false)].buff[(3*(cursor.eid))+2];


   return 0;
}
